<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'A hacky solution',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<img src="/img/CC_BY-SA_4.0/y.st./weblog/2018/12/07.jpg" alt="The highway off ramp behind my workplace" class="framed-centred-image" width="649" height="480"/>
<section id="drudgery">
	<h2>Drudgery</h2>
	<p>
		My discussion post for the day:
	</p>
	<blockquote>
		<p>
			(Disclaimer: This is all based on past knowledge, so there are no sources for me to cite.
			I haven&apos;t had time to read this week&apos;s reading assignment yet.)
		</p>
		<h3>Part 0</h3>
		<p>
			When you pass arguments to a function, you can do it in one of two ways: by value or by reference.
			Some languages use one, while some use another.
			Still other languages might pass either one, depending on the value.
			For example, $a[PHP] passes most arguments by value, but it always passes objects by reference instead.
			Sometime it passes arrays by reference too, such as when using an array-sorting function.
			Lua, on the other hand, passes most arguments by value, but passes all tables by reference.
		</p>
		<p>
			So what does this all mean?
			Well, the easy way to think about it is that variables passed by value have their value copied.
			A new variable exists within the function, based on that function&apos;s parameter.
			When an argument is passed in, the value is copied from the old variable in the old scope to the new variable in the new scope.
			These variables, after the copy, are completely and totally separate.
			Changing one does not in any way affect the other.
			On the other hand, when passing by reference, it&apos;s not the value of the variable that gets passed - it&apos;s the pointer!
			The variables, both the one in the outer scope and the one used internally by the function, now have a pointer pointing to the exact same memory location.
			At this point, changing the value of one variable necessarily changes the value of the other, as both variables read from the same memory location.
		</p>
		<p>
			The security implications here should be pretty clear.
			If you pass by reference, the function can modify the data used in the outer scope.
			Most of the time, this is undesirable behaviour.
			You may want to have the function see the data and use it to compute a result, but you almost never want your data modified by it.
			If you wanted the data modified, you&apos;d perform your own assignment statement outside the function using the function&apos;s output.
		</p>
		<h3>Part 1</h3>
		<p>
			The knapsack problem is a problem in which you attempt to make off with as much valuable loot as you can.
			Each item has a monetary value, but it also has a weight, and yo can only carry so much weight and still make your getaway.
			The goal is to choose the items that&apos;ll give you the highest monetary gain as possible, given the weight constraint.
			It&apos;s an easy enough problem to solve, using recursion.
			(In this post, I&apos;ll be using the &quot;¤&quot; symbol, so I guess I should explain it for students that don&apos;t recognise it.
			It&apos;s a generic currency symbol, not specific to any country or currency.
			As the problem isn&apos;t currency-specific, there&apos;s no reason to work it in pounds, Euros, dollars, or anything like that.)
		</p>
		<p>
			The first thing I would do it iterate over all the items, keeping track of the cost to weight and weight to cost in a pair of dictionaries.
			The point here is to eliminate duplicates.
			For example, say there are two items worth ¤20.
			The items can&apos;t also have the same weight, as that&apos;d be pointless to the puzzle.
			So we can throw out the item with the greater weight, not using it in our solution at all.
			Likewise, if two items both weigh 5 kilograms, we throw out the item with the smaller monetary value.
			By reducing the number of items we&apos;re working with, we can reduce the number of recursive function calls, as we&apos;re not trying options that will obviously be wrong.
		</p>
		<p>
			The next thing to rule out is duplicates.
			The other day, I ran a brute force program I wrote to find the solution to some problem I was having.
			I left for work, letting it do its thing.
			It was poorly-coded, and I knew it, but I didn&apos;t have time to fine-tune it.
			At work, I came up with a better solution; one that allowed the program to avoid trying duplicate answers.
			For example, two of item A and one of item B is the same solution as one of item A, one of item B, and another of item A.
			So I get home, hoping my laptop has found an answer for me, but it wasn&apos;t even <strong>*close*</strong> to done.
			I knew it&apos;d be quicker to interrupt the execution, rewrite the code using my solution, and start the thing over.
			I still thought it&apos;d take several hours to get my solution, but instead, it took a few <strong>*seconds*</strong>.
			Checking duplicate solutions takes a <strong>*tonne*</strong> of time.
			So for our knapsack problem, we want to avoid duplicate solutions being tried.
			There&apos;s an easy way to do this.
			First, assign an order to the items you haven&apos;t ruled out in the last step.
			Second, never choose an item that has a lower position index the list than the last item you chose.
			This is the exact solution I used in the code that shortened the run time from many hours to a mere few seconds.
		</p>
		<p>
			With these two optimisations complete, it&apos;s time to begin our recursion.
			An outer function handles the above tasks.
			It checks for items that should never under any circumstances be used in the solution, and it gives order to the items that may be of use.
			It then calls the inner function, which performs all the recursion.
			This allows the recursive function to not perform all that overhead with each recursive call.
			The recursive function takes four arguments: an ordered list of available items, the total weight we can carry, a list of the items currently chosen for this attempt, and the index of the last item chosen.
			Starting at the given index, it&apos;ll go down the list and check to see which items don&apos;t cause us to go over the weight limit.
			Any time an item is encountered that fits the criteria, the item is added to a copy of the list, a flag is set, and the function called recursively, passing in the new list and the index of that item.
			The result of this recursive call is added to a list.
			Once we get to the end of the list of available items to try, we check our list of possible solutions.
			If the list is empty, we know that no item we try to add will fit without breaking the weight limit.
			This is our base case.
			In this case, we return the original list of items passed to this instance of the function call.
			Otherwise, we go down the list and find the one with the highest monetary value.
			We return that solution.
		</p>
		<p>
			Normally, you want to define a base case before the recursive calls, but in this case, it really doesn&apos;t work.
			You need to check each item to know whether the base case has occurred.
			If you define the base case twice, you end up going down the list to see if you&apos;ve hit the base case, then if you haven&apos;t, run down the list again to run the recursive calls.
			It works in this case though, for one simple reason: when checking each option, the function is checking to see if we have a weight overflow <strong>*before*</strong> running the recursion.
			Because of this, the recursion will always be skipped in cases it shouldn&apos;t be performed, so we do in fact always come back to our base case eventually.
		</p>
		<p>
			So how efficient is this?
			It&apos;s hard to say, due to the nature of the problem.
			We don&apos;t know how any recursive attempts are made.
			I&apos;d say a good estimation would be that in the worst case, the lightest item would be the only one used, as that causes the most recursion.
			At most, you&apos;ll have <code>max_capacity</code> divided by <code>weight_of_lightest_item</code> (rounded down to the nearest integer) layers to go through.
			Let&apos;s call that number <code>max_depth</code>.
			If we hadn&apos;t prevented duplicate answers, the run time would be O(<code>number_of_items</code><sup><code>max_depth</code></sup>).
			I honestly have no idea how to factor in the optimisation done by ruling out the duplicates before trying them though.
			As I said before though, it makes the difference between the algorithm taking hours to complete and taking seconds, so it&apos;s not the type of thing that can just be ignored as insignificant.
			Does anyone have any suggestions as to how to calculate the efficiency of this?
		</p>
		<p>
			So how does the efficiency of recursion for this case compare to the efficiency without recursion?
			Honestly, I think if you can figure out how to code a solution-finder for this problem without using recursion, you&apos;ll get better efficiency.
			The problem is that figuring out how to do that is incredibly difficult.
			Think of the set of moves as a tree diagram, with the possible solutions being leaf nodes.
			(We&apos;re not working with a <strong>*binary*</strong> tree though, so each branch will have several child nodes.)
			We could of course write code to produce this tree structure.
			That&apos;d increase the storage demands of our problem though.
			Instead, what we&apos;d need to do is simulate recursion without all the overhead of touching the calling stack.
			This would give us greater speed and lesser storage demands.
			However, can you even imagine trying to write code to do that?
			You can&apos;t even use a bunch of nested loops to solve this, unless you want to code your corner cases into each and every loop layer.
			Or find a way to deal with all the corner cases with a subroutine that&apos;s called from every loop layer.
			This is probably exactly what you&apos;d have to do.
			While completely possible, the number of <strong>*development hours*</strong> that would go into such a project would be immense.
			Usually, recursion makes our solutions less efficient, but makes the <strong>*development*</strong> of our solutions much more efficient.
			The same applies to all three problem options we are presented with to choose from in this discussion assignment.
		</p>
	</blockquote>
</section>
<section id="defective">
	<h2>Defective item</h2>
	<p>
		The item I discussed yesterday is no longer charging, even with my hair band hack in place.
		The hair band is just too stretchy, so the device is still able to eject the charging cord far enough to prevent charging.
		I&apos;ll have to try something else.
		Perhaps I can tie the charger on with a shoe lace?
	</p>
</section>
<section id="forgetfulness">
	<h2>Forgetfulness</h2>
	<p>
		I found myself forgetting things several times today, which cost me a lot of time.
		First, I forgot to bring my prescription to the pharmacy so I could get a refill of my prescription toothpaste.
		Today&apos;s the last day the prescription&apos;s good too, so I can&apos;t wait until tomorrow.
		I tried to put as much space between refills as I could so as to make sure it didn&apos;t raise any red flags.
		The truth though is that I still haven&apos;t finished the first tube of the stuff, and am only getting the refills for when this tube does run dry.
		Then, I forgot to snap my photograph for the day while I was there.
		I forgot the photo when I did bring the prescription as well, and forgot again on the way to work.
		So yeah.
		You get a photo of the highway behind my workplace today, as I failed to get a photo of something else sooner.
	</p>
</section>
<section id="Minetest">
	<h2>Minetest</h2>
	<p>
		I figured out a hack for working around a Minetest bug that&apos;s bothered me for a while.
		And quite hacky it is indeed!
	</p>
	<p>
		Okay, so when moving an item between two separate inventories in Minetest, a callback function can be defined that allows only a certain number of the item to be taken or added to the inventory.
		Such callbacks cannot be defined for a player&apos;s inventory, but for all other inventories a mod defines, a callback can be added.
		The callback is able to see what the player is trying to move and how many.
		This means you can, for example, disallow certain items from being added to an inventory, as your callback can look at the item and limit the move count to zero.
		Certain nodes in Minetest Game employ this strategy.
		This functionality is vital to my plans for <code>minechest</code>.
		<code>minechest</code> will stack items higher than normally allowed, but will only allow you to withdraw a number of items at a time that is less than or equal to the number that could normally be stacked.
		This means that within the chest, you&apos;ve got a lot of space, but you can&apos;t use the chest to compress your items, then move them elsewhere without decompressing them.
	</p>
	<p>
		However, the engine has a bug.
		If you take part of a stack (or even a whole stack) and try to put it onto an incompatible stack, the limiting callback is called, but if you&apos;re allowed to put even one, the two stacks will get switched.
		The first problem is your putting limit is ignored.
		People are able to smuggle more in than you want to allow.
		Secondly, the full other stack pops out, which mean you can smuggle <strong>*out*</strong> things.
		Instead of putting, you can take stuff, which allows you to swap stacks as well.
		This means to get anything in or out, you just need something that&apos;s allowed to go one direction.
		You can make anything else go the other direction.
		And you can take more than you&apos;re allowed to.
		This makes the <code>minequest</code> chests too powerful, as they can be used as item compressors, and you can then store all your items in another chest.
		The simple fact is that if you move items between two inventories, it isn&apos;t possible to perform all the checks needed to make everything as secure as it needs to be
	</p>
	<p>
		And therein lies the secret that powers my hack.
		You can&apos;t allow the player to move items between inventories.
		Instead, the chest, when opens, needs to steal all the player&apos;s items, and put them in a separate inventory list as the chest&apos;s main inventory.
		It can then present the player with a form that makes it look like the player is moving items between the two inventories, even though they&apos;re actually just moving items between lists in the same inventory.
		The movement callback within a single inventory is able to catch all the little corner cases, unlike the putting callback and taking callback.
		Once the player closes the chest, it can give the player back the items from that list, and everything will be fine.
		As a side note, I think this&apos;ll allow me to make stacks seem to be stackable to their full higher by the player.
		No need for the chest to suck all the items into one stack whether the player wants it to or not.
		They player will have options.
	</p>
	<p>
		I do foresee issues though.
		I might need to add further abstraction to prevent issues when, for example, a player disconnects before closing the chest.
		Perhaps both the chest&apos;s main inventory and the player&apos;s inventory would both get proxies.
		And maybe these proxies hold copies of the items instead of the items actually being taken.
		It&apos;s a work in progress, but I think it&apos;ll work well once I have the details sorted out.
	</p>
</section>
<section id="sales">
	<h2>Top salesperson</h2>
	<p>
		A few days before the end of the month, the head manager told me I was winning the sales competition again this month.
		I wasn&apos;t even aware we were still doing that.
		I thought it was a on-time thing.
		Then the month ended, and no prize came.
		Like I said, I wasn&apos;t working toward a prize, so I didn&apos;t think I needed one.
		I did think the head manager was trying to backtrack though, as I&apos;d admitted before that I didn&apos;t realise that was happening again.
		They gave me the prize today though.
		So I guess that&apos;ll help cover my eye exam.
	</p>
	<p>
		Speaking of which, the eyeglass shop I knew of seems to have closed.
		I&apos;m going to have to locate another.
		Someone at work told me about two eyeglass shops in the next city over.
		I didn&apos;t know where one of them was, but I bike past the alleged location of the other every week.
		I&apos;ll probably try that one first.
	</p>
</section>
<section id="time">
	<h2>More time</h2>
	<p>
		I started this week a bit behind in my coursework.
		I&apos;d blame it on my wonky work schedule last week, but that&apos;d be an utter lie.
		I had time, and I blew it.
		It&apos;s entirely my fault, despite the schedule
	</p>
	<p>
		This week though, the head manager has given me an extra day off from work.
		Do they know that&apos;d be useful to me?
		Were they trying to do me a favour?
		Not at all.
		As far as they know, all that does id net me less hours and a smaller pay cheque.
		I don&apos;t complain about my self-imposed issues to them, especially seeing as they&apos;re not the type of person I would confide in.
		Still, I appreciate the extra time.
		The time&apos;ll help me more than the hours would.
		Even if I manage to get my coursework done early, it&apos;ll give me more time to work on <code>minequest</code>.
	</p>
</section>
END
);
